package leetCode.offer33;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
 * 参考以下这颗二叉搜索树：
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 *
 * 示例 1：
 * 输入: [1,6,3,2,5]
 * 输出: false
 *
 * 示例 2：
 * 输入: [1,3,2,6,5]
 * 输出: true
 *
 */
public class Solution1 implements Solution{

    @Override
    public boolean verifyPostorder(int[] postorder) {
        return isVerify(postorder,0,postorder.length-1);
    }

    public boolean isVerify(int[] postorder,int start,int end){
        if(start>=end) return true;
        int index = -1;
        for(int i=start;i<end;i++){
            if(index>=0&&postorder[i]<postorder[end]){
                return false;
            }
            if(postorder[i]>postorder[end]&&index==-1){
                index = i;
            }
        }
        index = end;
        boolean left = isVerify(postorder,start,index-1);
        boolean right = isVerify(postorder,index,end-1);
        return left&&right;
    }

    public static void main(String[] args) {
        int[] param = {5, 2, -17, -11, 25, 76, 62, 98, 92, 61};
        int[] param2 = {1,6,3,2,5};
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.verifyPostorder(param));
        System.out.println(solution1.verifyPostorder(param2));
    }


}
